package com.xq.algorithm.sort;

import static com.xq.algorithm.AlgorithmTest.printlnAry;

/**
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/09.
 *         二分查找
 *         二分搜索（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），
 *         是一种在有序数组中查找某一特定元素的搜索算法。
 *         搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
 *         如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
 *         如果在某一步骤数组为空，则代表找不到。
 *         这种搜索算法每一次比较都使搜索范围缩小一半。
 *
 *         时间复杂度:折半搜索每次把搜索区域减少一半，时间复杂度为Ｏ(Log n) 。（n代表集合中元素的个数）
 *         空间复杂度:迭代：O(1)　　递归：O(log n)
 */

public class BinarySearchAlgorithm {

    public static int binarySearch(int[] arr,int key){
        if(arr == null)return -1;
        int low = 0;
        int high = arr.length - 1;
        int mid;
        while (low <= high){
            mid = low + (high - low) / 2; //直接平均可能会溢位
            if(arr[mid] < key){
                low = mid + 1;
            }else if(arr[mid] > key){
                high = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * SparseArray改进后的二分法查找法
     * @param a
     * @param start
     * @param len
     * @param key
     * @return
     */
    public static int binarySearch(int[] a,int start,int len,int key){
        int high = start + len;
        int low = start - 1;
        int mid;
        while(high - low > 1){
            mid = low + (high - low) / 2; //直接平均可能会溢位
            if(a[mid] < key){
                low = mid;
            }else {
                high = mid;
            }
        }

        if(high == start + len){
            return ~(start + len);
        }else if(a[high] == key){
            return high;
        }else {
            return ~high;
        }
    }

    public static void testBinarySearch(int key){
        int[]a = new int[]{1,2,3,4,5,6,7};
        printlnAry(a);
        int result = binarySearch(a,key);
        if(result != -1){
            System.out.println(key+"所在的位置索引是"+ result);
        }else {
            System.out.println("没有找到该值");
        }
    }

    public static void testBinarySearch1(int key){
        int[]a = new int[]{1,2,3,4,6,7};
        printlnAry(a);
        int result = binarySearch(a,0,a.length,key);
        if(result > 0){
            System.out.println(key+"所在的位置索引是"+ result);
        }else {
            System.out.println("没有找到该值"+~result);
        }
    }
}
